#
# @lc app=leetcode.cn id=2 lang=python
#
# [2] 两数相加
#

# @lc code=start
# Definition for singly-linked list.


class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution(object):
    def addTwoNumbers(self, l1, l2) :
        """
        将两个逆序存储的数字相加
        
        思路：模拟竖式加法
        1. 同时遍历两个链表
        2. 逐位相加，记录进位
        3. 创建新节点存储结果
        
        :type l1: Optional[ListNode]
        :type l2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        if l1 is None and l2 is None:
            return None
        if l1 is None:
            return l2
        if l2 is None:
            return l1
        #[2,4,3] [5,6,4]#
        #创建一个头节点，用于返回结果
        resultListNode = ListNode(0)
        #创建一个当前节点，用于记录链表
        currentNode = resultListNode
        #创建一个进位，用于记录进位
        carry = 0
        while l1 or l2 :
            value1 = l1.val if l1 else 0
            value2 = l2.val if l2 else 0
            #计算当前位和进位
            total = value1 + value2 + carry
            #计算进位，10以内加法，进位最多为1
            carry = total // 10
            # 取余得数字：10%10=0, 7%10=7
            digit = total % 10
            #创建新节点,计算当前位数字=总和%10。作为下一个节点的value
            currentNode.next = ListNode(digit)
            #移动当前节点
            currentNode = currentNode.next
            #移动l1和l2
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
        #循环完成后如果还有进位，追加一个新节点
        if carry > 0:
            currentNode.next = ListNode(carry)
        #返回结果链表
           
        return resultListNode.next
            
        
        
       
        
# @lc code=end
